package com.cn.algorithm02.class05;

import com.cn.algorithm02.class01.CodeUtil;
import com.sun.org.apache.regexp.internal.RE;

/***
 * @author: hels
 * @description: 遍历数组，求数组中有多少个逆序对
 * T(N) = 2*T(N/2) + O(N)     根据master公式：  N*logN
 * 逆序对: 左>右
 * {4, 5, 2, 1}  42 41 52 51 21
 * {4, 5, 2, 1, 0}
 **/
public class C03_BackWard {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 1,0};
        System.out.println(process(arr, 0, arr.length - 1));
    }

    public static int process(int[] arr, int L, int R) {
        if (arr == null || L == R) return 0;

        int mid = L + ((R-L)>>1);
        int left = process(arr, L, mid );
        int right = process(arr, mid + 1, R);
        int m = merge(arr, L, mid, R);
        return left + right + m;
    }

    public static int merge(int[] arr, int L, int mid, int R) {
        if (L >= R) return 0;

        // L < R 核心代码：数量统计
        int ans = 0;
        int  p = mid+1;
        for (int i = L; i <= mid; i++) {
            while (p <= R && arr[i]> arr[p]) {
                p++;
            }
            ans += (p - mid - 1);
        }

        // 顺序排序
        int[] sortArr = new int[R-L+1];
        int index = 0;
        int p1 = L, p2 = mid+1;
        while (p1 <= mid && p2 <= R) {
            sortArr[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            sortArr[index++] = arr[p1++];
        }
        while (p2 <= R) {
            sortArr[index++] = arr[p2++];
        }
        for (int i = 0; i < sortArr.length; i++) {
            arr[L+i] = sortArr[i];
        }
        return ans;
    }
}